package com.github.yangyishe.p300;

import java.util.*;

/**
 * 207. 课程表
 * https://leetcode.cn/problems/course-schedule/?envType=study-plan-v2&envId=top-interview-150
 *
 * 你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
 *
 * 在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程  bi 。
 *
 * 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
 * 请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：numCourses = 2, prerequisites = [[1,0]]
 * 输出：true
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
 * 示例 2：
 *
 * 输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
 * 输出：false
 * 解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
 *
 *
 * 提示：
 *
 * 1 <= numCourses <= 2000
 * 0 <= prerequisites.length <= 5000
 * prerequisites[i].length == 2
 * 0 <= ai, bi < numCourses
 * prerequisites[i] 中的所有课程对 互不相同
 */
public class Problem207 {
    public static void main(String[] args) {
        int numCourses=3;
        int[][] prerequisites=new int[][]{
                {1,0},
                {1,2},
                {0,1}
        };

        Problem207 problem207 = new Problem207();
        boolean b = problem207.canFinish(numCourses, prerequisites);
        System.out.println(b);
    }

    /**
     * 数学思路:
     * 各课程之间的关系, 是一个有向图.
     * 但与遍历不同的是, 在遍历一个节点后, 不能马上遍历该节点所指向的所有节点, 而应该在确保下一节点的所有前置节点均遍历后, 才能遍历该节点.
     *
     * 先查找出所有不需要前置课程的课程.
     * 再根据前置课程分别进行图的遍历
     * 如果能把所有课遍历完, 则说明可以完成所有课程
     *
     *
     * 代码思路:
     * 创建一个前置课到后修课的集合map, 一个已选课的Set
     * 然后用图的遍历处理, 遍历完判定set的size是否等于课程数量
     *
     * 错误理解修正:
     * 需要把全部前置课程学习完, 才能学后置可能, 而不是只学习一门前置课程.
     *
     * 新思路:
     * 1. 暴力破解法:
     * a)先寻找所有没有前置的课程;
     * b)根据当前可修课程, 推演出其他未学习的可修课;
     * c)重复b,并记录每次新增的可修课;
     * d)如果某次新增的课数为0,且仍有未学习的课程,则说明课程不能学习完;否则说明课程可以学习完.
     *
     * 2. 可优化的点:
     * 在对b)进行未学且可学的课程时,可以使用一个前2后ListMap存储 每个课程的后继课程; 同时用一个后2前countMap存储 每个课程的前置课程数.
     * 在对c)进行记录时, 使用一个set记录已学习的课程, 使用flag表示当次是否有新增课程
     *
     * @param numCourses
     * @param prerequisites
     * @return
     */
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        for(int i=0;i<numCourses;i++){
            fore2BackListMap.putIfAbsent(i,new ArrayList<>());
            back2CountMap.putIfAbsent(i,0);
        }
        for(int[] q:prerequisites){
            int back=q[0];
            int fore=q[1];

            fore2BackListMap.get(fore).add(back);
            back2CountMap.put(back,back2CountMap.get(back)+1);
        }
        for(int back:back2CountMap.keySet()){
            if(back2CountMap.get(back)==0){
                courseQueue.addLast(back);
                learnedSet.add(back);
            }
        }
        while(!courseQueue.isEmpty()){
            Integer course = courseQueue.removeFirst();
            chooseCourse(course);
        }


        return learnedSet.size()==numCourses;
    }

    // 前2后listMap
    private Map<Integer,List<Integer>> fore2BackListMap=new HashMap<>();

    // 后2countMap
    private Map<Integer,Integer> back2CountMap=new HashMap<>();

    // 已学课程
    private Set<Integer> learnedSet =new HashSet<>();
    private LinkedList<Integer> courseQueue=new LinkedList<>();

    private boolean chooseCourse(Integer course){
        boolean flag=false;
        List<Integer> backList=fore2BackListMap.get(course);
        if (backList!=null) {
            for (Integer back : backList) {
                back2CountMap.put(back,back2CountMap.get(back)-1);
                if(back2CountMap.get(back)==0){
                    learnedSet.add(back);
                    courseQueue.addLast(back);
                    flag=true;
                }
            }
        }
        return flag;
    }


}
